package heepstackqueue;

import java.util.*;

public class D230724 {
    // 最小的K个数
    // 思路：大根堆，先放 k 个数，然后再让堆顶与剩下的比较，堆顶比较大，更新堆顶元素。
    public ArrayList<Integer> GetLeastNumbers_Solution (int[] input, int k) {
        ArrayList<Integer> ret = new ArrayList<>();
        if (k == 0) {
            return ret;
        }
        PriorityQueue<Integer> heap = new PriorityQueue<>((o1, o2) -> {
            return o2 - o1;
        });
        int i = 0;
        for (; i < k; i++) {
            heap.add(input[i]);
        }
        for (; i < input.length; i++) {
            if (input[i] < heap.peek()) {
                heap.poll();
                heap.add(input[i]);
            }
        }
        for (int a : heap) {
            ret.add(a);
        }
        return ret;
    }

    // 寻找第K大
    public int findKth1 (int[] a, int n, int K) {
        Arrays.sort(a);
        return a[n - K];
    }

    // 思路：快排，每次划分都可以确定一个基准值的最终位置
    // 如果基准值的位置 在 n - k 上，那么就是答案
    // 否则基准值的位置 在 n - k 的左边，则继续划分右边的区域，左边不管
    // 另一边同理
    public int findKth (int[] a, int n, int K) {
        return quickSort(a, 0, n - 1, K);
    }
    private int quickSort(int[] a, int l, int r, int k) {
        int p = partition(a, l, r);
        if (p == a.length - k) {
            return a[p];
        } else if (p > a.length - k) {
            // p 在答案的右边，递归左边
            return quickSort(a, l, p - 1, k);
        } else {
            return quickSort(a, p + 1, r, k);
        }
    }
    private int partition(int[] arr, int left, int right) {
        int key = arr[left];
        while (left < right) {
            while (left < right && arr[right] >= key) {
                right--;    // 右边 找比基准值小的
            }
            arr[left] = arr[right];
            while (left < right && arr[left] <= key) {
                left++;     // 左边 找比基准值大的
            }
            arr[right] = arr[left];
        }
        arr[left] = key;
        return left;
    }



    // 滑动窗口的最大值
    // 方法一：暴力破解
    public ArrayList<Integer> maxInWindows1(int [] num, int size) {
        ArrayList<Integer> ret = new ArrayList<>();
        if (size == 0) {
            return ret;
        }
        int n = num.length;
        for (int i = 0; i <= n - size; i++) {
            int max = 0;
            for (int j = i; j < i + size; j++) {
                max = Math.max(max, num[j]);
            }
            ret.add(max);
        }
        return ret;
    }

    // 方法二：滑动窗口
    // 使用一个双端队列，维护当前窗口的一个 单调递减的队列
    // 存放的是数组下标，方便进行出窗口操作，不再窗口中的就出
    public ArrayList<Integer> maxInWindows(int [] num, int size) {
        ArrayList<Integer> ret = new ArrayList<>();
        if (size == 0) {
            return ret;
        }
        Deque<Integer> deque = new ArrayDeque<>();
        int n = num.length;
        for (int i = 0; i < n; i++) {
            while (!deque.isEmpty() && num[i] > num[deque.getLast()]) {
                // 维护一个单调递减的队列，存放的是下标
                // 如果当前元素大于队尾元素，队尾元素出队
                deque.pollLast();
            }
            // 进窗口
            // 当前元素入队
            deque.addLast(i);
            // 出窗口
            // 查看队首元素是否合法
            if (deque.getFirst() + size - 1 < i) {
                deque.pollFirst();
            }
            // 更新
            if (i >= size - 1) {
                ret.add(num[deque.getFirst()]);
            }
        }
        return ret;
    }
}
